#!/usr/bin/python3
import sys


def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

try:
    t = int(input())
    if t<1 or t>100:
        sys.exit(0)
    ids = 0
    m = 0
    while t > 0:
        n = int(input())
        if n < 1 or n > 10000:
            sys.exit(0)
        t = t - 1
        ids = ids + 1
        if n == 1 or n%2 == 0:
            print(f"Case #{ids}: 0")
            continue
        x = 0
        c = 0
        while x < n-1:
            x = x +2
            if gcd(x, n)==1:
                c = c + 1
        print(f"Case #{ids}: {c}")

except ValueError:
    pass
except EOFError:
    pass
except MemoryError:
    pass
